Crate permutator

Source
Expand description

This crate provide generic cartesian product iterator, combination iterator, and permutation iterator.

§Three main functionalities

  • Cartesian product
  • Combination
  • Permutation

§Two different style on every functionality

This crate provide two implementation style

  • Iterator style
  • Callback function style

§Easily share result

  • Every functionalities can take Rc<RefCell<>> to store result.
  • An iterator that return owned value.
  • Every callback style function can take Arc<RwLock<>> to store result.

§Easy usage

Three built-in traits that add cart_prod, combination, and permutation functionality to slice/array, Rc<RefCell<&mut[T]>>, and more.

§Unreach raw performance with unsafe

Every functionalities can take raw mutable pointer to store result.

§Example

  • Getting k-permutation where k is 3 and n is 5.
use permutator::{Combination, Permutation};
let mut data = &[1, 2, 3, 4, 5];
let mut counter = 1;
data.combination(3).for_each(|mut c| {
    c.permutation().for_each(|p| {
        println!("k-permutation@{}={:?}", counter, p);
        counter += 1;
    });
});
  • Getting lexicographically ordered k-permutation where k is 3 and n is 5.
use permutator::{Combination, XPermutationIterator};
let mut data = &[1, 2, 3, 4, 5];
let mut counter = 1;
data.combination(3).for_each(|mut c| {
    XPermutationIterator::new(&c, |_| true).for_each(|p| {
        println!("k-permutation@{}={:?}", counter, p);
        counter += 1;
    });
});
  • Cartesian product of set of 3, 4, and 5 respectively
use permutator::{CartesianProductIterator, cartesian_product};
let mut domains : &[&[i32]]= &[&[1, 2], &[3, 4, 5], &[6, 7, 8, 9]];
println!("=== Cartesian product iterative style ===");
CartesianProductIterator::new(domains).into_iter().for_each(|p| {
    println!("{:?}", p);
});
println!("=== cartesian product callback style ===");
cartesian_product(domains, |p| {
    // `p` is borrowed a ref to internal variable inside cartesian_product function.
    println!("{:?}", p);
});
  • Easy sharable result
   use std::cell::RefCell;
   use std::rc::Rc;
   use std::time::Instant;
   use permutator::CartesianProduct;
    
   let mut counter = 0;
   let timer = Instant::now();
   let data : &[&[u8]]= &[&[1, 2], &[3, 4, 5, 6], &[7, 8, 9]];
   let mut result = vec![&data[0][0]; data.len()];
   let shared = Rc::new(RefCell::new(result.as_mut_slice()));

   (data, Rc::clone(&shared)).cart_prod().for_each(|_| {
       println!("{:?}", &*shared.borrow());
       // and notify result borrower(s) that new product is available.
 
       counter += 1;
   });

   println!("Total {} products done in {:?}", counter, timer.elapsed());
  • Unsafely share result example
   use std::time::Instant;
   use permutator::Permutation;

   let data : &[i32] = &[1, 2, 3, 4, 5];
   let mut counter = 0;
   let k = 3;
   let mut result : Vec<&i32> = vec![&data[0]; k];
   // `result` can be share safely anywhere
   let shared = result.as_mut_slice() as *mut [&i32];
   // `shared` can be share as long as `result` is alive
   let timer = Instant::now();
   // unsafe statement may be omit because the permutation trait
   // hid it internally. However, keep in mind that it rely
   // on a pointer so every operation is still considered unsafe.
   unsafe {
       (data, k, shared).permutation().for_each(|_| {
           println!("{:?}", &*shared);
           // and notify result borrower(s) that new permutation is available.
 
           counter += 1;
       });

       println!("Total {} combination done in {:?}", counter, timer.elapsed());
   }

§See

§Found a bug ?

Open issue at Github

Modules§

  • copy
    A module that perform everything in copy fashion. There is no Heap permutation family function in here because that function family already return a slice of value.

Structs§

  • CartesianProductCellIter
    Generate a cartesian product between given domains into Rc<RefCell<&mut [&T]>> in an iterator style. The struct implement Iterator trait so it can be used as Iterator. The struct provide into_iter() function that return itself.
  • CartesianProductIterator
    Generate a cartesian product between given domains in an iterator style. The struct implement Iterator trait so it can be used in Iterator style. The struct provide into_iter() function that return itself.
  • CartesianProductRefIter
    An unsafe way to generate a cartesian product between given domains into *mut [&T] in an iterator style. The struct implement Iterator trait so it can be used as Iterator. The struct provide into_iter() function that return itself.
  • CombinationCellIter
    Deprecated
  • CombinationIterator
    Deprecated
  • CombinationRefIter
    Deprecated
  • GosperCombinationCellIter
    Deprecated
  • GosperCombinationIterator
    Deprecated
  • GosperCombinationRefIter
    Deprecated
  • HeapPermutationCellIter
    Heap’s permutation in Rc<RefCell<>> mimic Iterator style. It provides another choice for user that want to share permutation result but doesn’t want to clone it for each share. It also doesn’t create new result on each iteration unlike other object that implement Iterator trait.
  • HeapPermutationIterator
    Heap’s permutation in iterator style implementation.
  • HeapPermutationRefIter
    An unsafe Heap’s permutation in iterator style implementation.
  • KPermutationCellIter
    k-Permutation over data of length “n” where k must be less than n. It’ll attempt to permute given data by pick k elements out of n data. It use Gosper algorithm to pick the elements. It then use Heap’s algorithm to permute those k elements and return each permutation back to caller by given Rc<RefCell<&mut [&T]>> parameter to new method of KPermutationCellIter.
  • KPermutationIterator
    k-Permutation over data of length n where k must be less than n. It’ll attempt to permute given data by pick k elements out of data. It use Gosper algorithm to pick the elements. It then use Heap’s algorithm to permute those k elements and return each permutation back to caller.
  • KPermutationRefIter
    k-Permutation over data of length “n” where k must be less than n and store result into mutable pointer. It’ll attempt to permute given data by pick k elements out of n data. It use Gosper algorithm to pick the elements. It then use Heap’s algorithm to permute those k elements and return each permutation back to caller by given *mut [&T]>> parameter to new method of KPermutationRefIter.
  • LargeCombinationCellIter
    Create a combination iterator. The result is lexicographic ordered if input is lexicorgraphic ordered. The returned combination will be a reference into given data. Each combination return from iterator is stored into given Rc<RefCell<&mut [&T]>>.
  • LargeCombinationIterator
    Create a combination iterator. The result is lexicographic ordered if input is lexicorgraphic ordered. The returned combination will be a reference into given data. Each combination return from iterator will be a new Vec. It’s safe to hold onto a combination or collect it.
  • LargeCombinationRefIter
    Create an unsafe combination iterator that return result to mutable pointer. The result is lexicographic ordered if input is lexicorgraphic ordered. The returned combination will be a reference into given data. Each combination return from iterator is stored into given *mut [&T].
  • SelfCartesianProductCellIter
    Generate a cartesian product on itself in an iterator style. The struct implement Iterator trait so it can be used in Iterator style. The struct provide into_iter() function that return itself.
  • SelfCartesianProductIterator
    Generate a cartesian product on itself in an iterator style. The struct implement Iterator trait so it can be used in Iterator style. The struct provide into_iter() function that return itself.
  • SelfCartesianProductRefIter
    Generate a cartesian product on itself in an iterator style. The struct implement Iterator trait so it can be used in Iterator style. The struct provide into_iter() function that return itself.
  • XPermutationCellIter
    A lexicographic ordered permutation based on “Algoritm X” published by Donald E. Knuth. page 20.
  • XPermutationIterator
    A lexicographic ordered permutation based on “Algoritm X” published by Donald E. Knuth. page 20.
  • XPermutationRefIter
    A lexicographic ordered permutation based on “Algoritm X” published by Donald E. Knuth. page 20.

Traits§

  • CartesianProduct
    Create a cartesian product out of T. For example,
  • Combination
    Create a combination out of T Normally, it take a [T] or Vec<T> to create a combination.
  • IteratorReset
    A trait that add reset function to an existing Iterator. It mean that the next or next_into_cell call will start returning the first element again
  • Permutation
    Create a permutation iterator that permute data in place. Built-in implementation return an object of HeapPermutation for slice/array and Vec. It return an object of HeapPermutationCellIter on data type of Rc<RefCell<&mut [T]>>.

Functions§

Type Aliases§